# -*- coding: utf-8 -*-

#-------------------------------------------------------------------------------
# Name:        sudoku_solver 2.0
# Purpose:     to solve sudoku puzzle by the method of preemptive sets
#
# Author:      Alexey
#
# Created:     22.02.2014
# Copyright:   (c) Alexey Zakharenkov 2014
# Licence:     <your licence>
#-------------------------------------------------------------------------------

# TODO:
# - make dimensions, USER_DIAGONALS constructor parameters
# - in a deadlock apply trial-and-error strategy



# How many boxes (squares/rectangles) are along X and Y axes
BOXES_X = 3
BOXES_Y = 3

# Box dimensions
BOX_WIDTH = 3
BOX_HEIGHT = 3

# Maximum digit value
MAX_DIGIT = ((BOX_WIDTH)*(BOX_HEIGHT))

# Field dimensions
WIDTH  = ((BOXES_X)*(BOX_WIDTH ))
HEIGHT = ((BOXES_Y)*(BOX_HEIGHT))

USE_DIAGONALS = False # TODO: make this a command-line parameter

assert WIDTH == HEIGHT and WIDTH == MAX_DIGIT, "Width does not equal Height"

ALL_ONES_MASK = ((1 << MAX_DIGIT) - 1) << 1
MAX_LOCKED_SET_SIZE = 3

import itertools
from functools import reduce

def readPuzzleFromFile(filename):
    """Read 2d-array with sudoku puzzle from a file"""
    field = []
    with open(filename, 'r') as f:
        linesCnt = 0
        while linesCnt < HEIGHT:
            line = f.readline()
            line = line.strip()
            if line:
                linesCnt += 1
                field.append([int(x) for x in line.split()])
    return field

class Cell:
    """Cell class"""
    def __init__(self, row, column, value = 0):
        self.value = value
        self.row = row       # row and column are convenient for debugging only
        self.column = column #
        self.possibleDigits = ALL_ONES_MASK
    def getPossibleDigitsSet(self):
        return set([d for d in range(1, MAX_DIGIT+1) if self.possibleDigits & (1 << d) != 0])


class SudokuPuzzle:
    """SudokuPuzzle class"""
    def __init__(self, array2D):
        self.__field = list([list([Cell(r, c, array2D[r][c]) for c in range(MAX_DIGIT)]) for r in range(MAX_DIGIT)])
        self.__region_cache = {}

    def __eq__(self, other):
        for r in range(len(self.__field)):
            for c in range(len(self.__field[0])):
                if self.__field[r][c].value != other.__field[r][c].value:
                    return False
        return True

    def __ne__(self, other):
        return not self.__eq__(other)

    def _get_column_as_region(self, column):
        region_key = "column" + str(column)
        if region_key not in self.__region_cache:
            self.__region_cache[region_key] = [self.__field[r][column] for r in range(HEIGHT)]
        return self.__region_cache[region_key]

    def _get_row_as_region(self, row):
        region_key = "row" + str(row)
        if region_key not in self.__region_cache:
            self.__region_cache[region_key] = self.__field[row]
        return self.__region_cache[region_key]

    def _get_box_as_region(self, R, C):
        region_key = "box" + str(R) + "." + str(C)
        if region_key not in self.__region_cache:
            self.__region_cache[region_key] = [self.__field[R*BOX_HEIGHT + r][C*BOX_WIDTH + c] for r in range(BOX_HEIGHT) for c in range(BOX_WIDTH)]
        return self.__region_cache[region_key]

    def _get_main_diagonal_as_region(self):
        region_key = "mainDiagonal"
        if region_key not in self.__region_cache:
            self.__region_cache[region_key] = [self.__field[i][i] for i in range(WIDTH)]
        return self.__region_cache[region_key]

    def _get_secondary_diagonal_as_region(self):
        region_key = "secondaryDiagonal"
        if region_key not in self.__region_cache:
            self.__region_cache[region_key] = [self.__field[i][WIDTH-i-1] for i in range(WIDTH)]

    def _regions_generator(self):
        for c in range(WIDTH):
            yield self._get_column_as_region(c)
        for r in range(HEIGHT):
            yield self._get_row_as_region(r)
        for R in range(BOXES_Y):
            for C in range(BOXES_X):
                yield self._get_box_as_region(R, C)
        if USE_DIAGONALS:
            yield self._get_main_diagonal_as_region()
            yield self._get_secondary_diagonal_as_region()

    def solve(self):
        for r in range(HEIGHT):
            for c in range(WIDTH):
                if self.__field[r][c].value != 0:
                    self._strike_out_candidates_when_digit_found(self.__field[r][c])

        improved = True
        while improved:
            improved = False
            for setSize in range(1, MAX_DIGIT):
                if improved: break # do this for searching smaller preemptive sets first
                for region in self._regions_generator():
                    improved |= self._find_preemptive_sets_in_region(region, setSize)

    def _strike_out_candidates_when_digit_found(self, solvedCell):
        if solvedCell.value == 0:
            return
        digit = solvedCell.value
        for region in self._regions_generator():
            if solvedCell in region:
                for cell in region:
                    if cell.value == 0:
                        cell.possibleDigits &= (ALL_ONES_MASK ^ (1 << digit))

    def _find_preemptive_sets_in_region(self, region, setSize):
        """Find preemptive sets in region and strike out possible digits in other cells of that region"""
        changed = False
        freeCells = [cell for cell in region if cell.value == 0]
        for cellsSubset in itertools.combinations(freeCells, setSize):
            subsetDigits = set(itertools.chain(*(cell.getPossibleDigitsSet() for cell in cellsSubset)))
            if len(subsetDigits) == setSize:
                improveCells = set(freeCells) - set(cellsSubset)
                mask = reduce(lambda x,y: x|y, (1 << d for d in subsetDigits), 0)
                for cell in improveCells:
                    if cell.possibleDigits & ~mask != cell.possibleDigits:
                        cell.possibleDigits &= ~mask
                        changed = True
                    # TODO: if subset of one region is within another region, strike out subset's digits from other cells of that region as well!
                if setSize == 1:
                    cellsSubset[0].value = list(subsetDigits)[0]
                    self._strike_out_candidates_when_digit_found(cellsSubset[0])
        return changed

    def print_field(self):
        """Print the field"""
        for row in self.__field:
            print (' '.join(str(cell.value) for cell in row))

    def is_solved(self):
        for row in range(HEIGHT):
            for col in range(WIDTH):
                if self.__field[row][col].value == 0:
                    return False
        return True



def main():
    array2D = readPuzzleFromFile("input.txt")
    puzzle = SudokuPuzzle(array2D)

    puzzle.solve()
    puzzle.print_field()


if __name__ == '__main__':
    main()


